package Class035_BinaryTreeProblems;

import BasicDataStructures.TreeNode;
import Utils.TreeUtils;
import javafx.util.Pair;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

//不含树形dp
public class TreeQuestions {
    public static int MAX = 2001;
    public static TreeNode[] fakeQueue = new TreeNode[MAX]; // 数组队列
    public static int l; // 队列头
    public static int r; // 队列尾

    public static void main(String[] args) {
        String data = "12345";
        TreeNode root = TreeUtils.generateTree(data);
//        System.out.println(levelOrder(root));
//        System.out.println(levelOrderWithQueue(root));
//        System.out.println(zigzagOrder(root));
//        System.out.println(zigzagOrderUsingArray(root));
//        System.out.println(getMaxLevelWidth(root));
        TreeUtils.printTree(root, "pre", true);
        String sd = serializePre(root);
        System.out.println(sd);
        TreeUtils.printTree(deserializePre(sd), "pre", true);
    }

    //bfs
    public static List<List<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> ll = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        ll.offer(root);
        int size = 0;
        while (!ll.isEmpty()) {
            size = ll.size();
            List<Integer> curLevel = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = ll.poll();
                assert cur != null;
                curLevel.add(cur.val);
                if (cur.left != null) {
                    ll.offer(cur.left);
                }
                if (cur.right != null) {
                    ll.offer(cur.right);
                }
            }
            ans.add(curLevel);
        }
        return ans;
    }

    //bfs using array
    public static List<List<Integer>> levelOrderWithQueue(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        fakeQueue[r++] = root;
        int size = 0;
        while (l != r) {
            size = r - l;
            List<Integer> curLevel = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = fakeQueue[l++];
                curLevel.add(cur.val);
                if (cur.left != null) {
                    fakeQueue[r++] = cur.left;
                }
                if (cur.right != null) {
                    fakeQueue[r++] = cur.right;
                }
            }
            ans.add(curLevel);
        }
        return ans;
    }

    //来回遍历
    public static List<List<Integer>> zigzagOrder(TreeNode root) {
        LinkedList<TreeNode> ll = new LinkedList<>();
        List<List<Integer>> ans = new ArrayList<>();
        ll.addLast(root);
        boolean reverse = false;
        while (!ll.isEmpty()) {
            int size = ll.size();
            List<Integer> curLevel = new ArrayList<>();
            if (reverse) {
                for (int i = 0; i < size; i++) {
                    TreeNode cur = ll.pollLast();
                    assert cur != null;
                    curLevel.add(cur.val);
                    if (cur.right != null) {
                        ll.addFirst(cur.right);
                    }
                    if (cur.left != null) {
                        ll.addFirst(cur.left);
                    }
                }
            } else {
                for (int i = 0; i < size; i++) {
                    TreeNode cur = ll.pollFirst();
                    assert cur != null;
                    curLevel.add(cur.val);
                    if (cur.left != null) {
                        ll.addLast(cur.left);
                    }
                    if (cur.right != null) {
                        ll.addLast(cur.right);
                    }
                }
            }
            ans.add(curLevel);
            reverse = !reverse;
        }
        return ans;
    }

    //zigzag traversal using array
    public static List<List<Integer>> zigzagOrderUsingArray(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        fakeQueue[r++] = root;
        boolean reverse = false;
        while (l < r) {
            int size = r - l;
            List<Integer> curLevel = new ArrayList<>();
            for (int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < size; i += j, k++) {
                curLevel.add(fakeQueue[i].val);
            }
            for (int i = 0; i < size; i++) {
                TreeNode cur = fakeQueue[l++];
                if (cur.left != null) {
                    fakeQueue[r++] = cur.left;
                }
                if (cur.right != null) {
                    fakeQueue[r++] = cur.right;
                }
            }
            ans.add(curLevel);
            reverse = !reverse;
        }
        return ans;
    }

    //若空节点也占位，请找出一棵树最大的宽度
    public static int getMaxLevelWidth(TreeNode root) {
        int maxWidth = 0;
        root.val = 1;
        fakeQueue[r++] = root;
        while (l < r) {
            int size = r - l;
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode cur = fakeQueue[l++];
                min = Math.min(min, cur.val);
                max = Math.max(max, cur.val);
                if (cur.left != null) {
                    cur.left.val = cur.val * 2;
                    fakeQueue[r++] = cur.left;
                }
                if (cur.right != null) {
                    cur.right.val = cur.val * 2 + 1;
                    fakeQueue[r++] = cur.right;
                }
            }
            maxWidth = Math.max(maxWidth, (max - min + 1));
        }
        return maxWidth;
    }

    //1. 递归函数的任务
    //2. 实现任务的内部逻辑
    //3. 终止条件
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return 1 + Math.max(left, right);
//        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

    public static int minDepth(TreeNode root) {
        if (root.left == null && root.right == null) {
            return 1;
        }
        if (root.left == null) {
            return 1 + minDepth(root.right);
        }
        if (root.right == null) {
            return 1 + minDepth(root.left);
        }
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }

    //把一棵树变成一个链表
    public static void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.left);
        if (root.left != null) {
            TreeNode originL = root.left;
            TreeNode originR = root.right;
            TreeNode leftTreeMostRight = originL;
            while (leftTreeMostRight.right != null) {
                leftTreeMostRight = leftTreeMostRight.right;
            }
            leftTreeMostRight.right = originR;
            root.right = originL;
            root.left = null;
        }
        flatten(root.right);
    }

//    #define max(a, b) a > b ? a : b;
//    int maxDepth(TreeNode* root) {
//        if(!root) {
//            return 0;
//        }
//        return 1 + Math.max(maxDepth(root->left), maxDepth(root->right));
//    }

    //给定一颗树的头，进行序列化和反序列化。
    //不限制方式，只要能转换回去即可
    public static String serialize(TreeNode root) {
        if(root == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        LinkedList<TreeNode> ll = new LinkedList<>();
        sb.append(root.val);
        ll.offer(root);
        while(!ll.isEmpty()) {
            int size = ll.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = ll.poll();
                assert node != null;
                if(node.left != null) {
                    ll.offer(node.left);
                    sb.append(",").append(node.left.val);
                }else {
                    sb.append(",#");
                }
                if(node.right != null) {
                    ll.offer(node.right);
                    sb.append(",").append(node.right.val);
                }else {
                    sb.append(",#");
                }
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public static String serializePre(TreeNode root) {
        if(root == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        s(root, sb);
        sb.append("]");
        return sb.toString();
    }

    private static void s(TreeNode node, StringBuilder sb) {
        if(node == null) {
            sb.append(",#");
            return;
        }
        if(sb.length() > 1) {
            sb.append(",");
        }
        sb.append(node.val);
        s(node.left, sb);
        s(node.right, sb);
    }

    public static TreeNode deSerialize(String data) {
        if("[]".equals(data)) {
            return null;
        }
        String[] d = data.substring(1, data.length() - 1).split(",");
        LinkedList<TreeNode> ll = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(d[0]));
        ll.offer(root);
        int index = 1;
        while(!ll.isEmpty()) {
            int size = ll.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = ll.poll();
                assert node != null;
                String left = index < d.length ? d[index++] : "#";
                String right = index < d.length ? d[index++] : "#";
                if(!"#".equals(left)) {
                    node.left = new TreeNode(Integer.parseInt(left));
                    ll.offer(node.left);
                }
                if(!"#".equals(right)) {
                    node.right = new TreeNode(Integer.parseInt(right));
                    ll.offer(node.right);
                }
            }
        }
        return root;
    }
    public static int index = 0;
    public static TreeNode deserializePre(String data) {
        if("[]".equals(data)) {
            return null;
        }
        index = 0;
        String[] d = data.substring(1, data.length() - 1).split(",");
        return ds(d);
    }
    private static TreeNode ds(String[] data) {
        if(index == data.length) {
            return null;
        }
        String curVal = data[index++];
        TreeNode cur = null;
        if(!"#".equals(curVal)) {
            cur = new TreeNode(Integer.parseInt(curVal));
        }
        if(cur == null) {
            return null;
        }
        cur.left = ds(data);
        cur.right = ds(data);
        return cur;
    }
}
